The present invention relates to correlators utilized in receivers of base stations and mobile units of wireless systems. More particularly, the present invention relates to a time-efficient real-time correlator that is suitable for use in receivers of base stations and mobile units of wireless systems.
Wireless systems utilize a communication protocol known as Code Division Multiple Access (CDMA). In CDMA, a communication channel uses a common frequency band. In the reverse-link (i.e., from the mobile to the base station), different mobile units are identified by using different psuedo-random number (PN) codes. In the forward-link (i.e., from the base station to the mobile unit), all base stations use the same PN codes but are identified by different offsets. Any time data is transmitted between a base station and a mobile unit, the transmission includes a PN code. The PN codes are fixed and are known to both the base station and the mobile units. However, there is a time-offset between them due to round trip delay of the transmission signal. If the time-offset is not correctly estimated, the received signal looks like nothing but noise. The receivers of the base stations and of the mobile units comprise correlators that correlate the incoming PN code with stored PN codes to determine the offset. The estimated offset is utilized to synchronize the received signal so that the received data can be decoded. It is also utilized to identify the base station in the case of the forward-link. Therefore, correlation of the PN codes is used for timing recovery.
The correlators that are currently utilized in the receivers of the base stations and mobile units for correlating the PN codes either do not perform the correlation in real-time or do not perform the correlation in real-time in an efficient manner. FIGS. 1 and 2 correspond to known correlators. Prior to describing the manner in which these known correlators perform the correlation methods, the correlation process will be mathematically described in order to facilitate the discussion of these correlators.
When a discrete-time sequence exists that corresponds to a time-delayed version of a known sequence plus noise, the time delay can be determined by the correlator. The functionality of the correlator is defined as follows. Letting the known discrete-time sequence be p(i), then the received signal r(i), which corresponds to a version of the sequence p(i) delayed by N-time units plus noise n(i), can be stated as:
r(i)=p(ixe2x88x92N)+n(i),xe2x80x83xe2x80x83(Equation 1)
where i is a discrete time index defined as ixcex5 { . . . , xe2x88x923,xe2x88x922,xe2x88x921,0,1,2,3, . . . }. The correlator calculates the correlation result, C(k), as follows:                                           C            ⁡                          (              k              )                                =                                    ∑                              i                =                0                                            M                -                1                                      ⁢                                          r                ⁡                                  (                                      i                    +                    k                                    )                                            ⁢                              p                ⁡                                  (                  i                  )                                                                    ,                  k          ∈                      {                          0              ,              1              ,              2              ,              …              ⁢                              xe2x80x83                            ,              W                        }                          ,                            (                  Equation          ⁢                      xe2x80x83                    ⁢          2                )            
where M is the coherent integration length and W is the maximum time delay, or search window. If C(k) is the largest correlation result of all {C(0), C(1), C(2), . . . , C(K), . . . C(W)}, then k corresponds to the estimated time delay, or time shift. This can be seen from Equation 3, which can be derived from Equations 1 and 2 as follows:                               C          ⁡                      (            k            )                          =                                            ∑                              i                =                0                                            M                -                1                                      ⁢                                          p                ⁡                                  (                                      i                    +                    k                    -                    N                                    )                                            ⁢                              p                ⁡                                  (                  i                  )                                                              +                                    ∑                              i                =                0                                            M                -                1                                      ⁢                                          n                ⁡                                  (                                      i                    +                    k                                    )                                            ⁢                              p                ⁡                                  (                  i                  )                                                                                        (                  Equation          ⁢                      xe2x80x83                    ⁢          3                )            
The first term is the signal component and the second term is the noise component. The signal component has the largest value when k is equal to N. As the value of the coherent integration length M increases, the time delay estimation becomes more precise.
With respect to the correlator shown in FIG. 1, the received signals are stored in memory before being processed. The received signal is represented by the horizontal row 1 comprised of blocks 2. The received signal r(i) is correlated with a PN sequence generated by a PN code generator (not shown) comprised by the receiver. Each of the blocks 2 corresponds to a sample of the received signal. Each of these samples is commonly referred to as a xe2x80x9cchipxe2x80x9d. The blocks 3, 4, 5 and 6 correspond to the generated PN sequence that is cross-correlated with r(i) to obtain the correlation results C(0) through C(W). The blocks 3, 4, 5 and 6 are shifted to represent the cross-correlation process over the correlation window W. The best correlation result corresponds to a match between the received PN sequence and the generated PN sequence. The time shift associated with the match corresponds to the time delay of the received signal r(i) (i.e., the number of chips that the received signal is offset with respect to the generated PN sequence).
Assuming each r(i) sample has B bits and each p(i) sample has H bits, then (M+W)B+MH bits of memory are needed to store the received signal and the PN sequence. In the case of the reverse-link, the length of the PN code is considered to be almost infinite (e.g., 2 to the power of 42). Therefore, an entire PN code can not be correlated with the received signal r(i). Rather, the PN code and the received signal r(i) are cross-correlated over M samples, where M is reasonably large for reliable estimation. For the same reason, the PN codes are generated instead of memorized. Algorithms executed by the mobile units and by the base stations inform the correlators as to what the PN sequence should be at any given time of day. The correlators then attempt to find a matching PN sequence by performing the M-length cross-correlation process for each possible offset, where W possible offsets exist.
Furthermore, the correlation process is not a real-time process because the correlation calculations do not begin until after the arrival of the last sample, r(M+Wxe2x88x921), of the received signal r(i). In order for the correlation process to be performed in real-time, the correlation results C(0) through C(W) must be available by the time the last sample of the received signal, r(M+Wxe2x88x921), has been received. Also, the multiplication and addition operations associated with each correlation of the generated PN code and the received signal must be performed in a single sample period.
The correlator shown in FIG. 2 uses a finite impulse response (FIR) filter 7 to perform the correlation process in real-time. The filter 7 is an M-th order FIR filter having the generated PN code, p(i), as its coefficients. A period of time equal to M chips is required for the received signal r(1) through r(Mxe2x88x921) to be shifted into the register 8. The register 8 comprises M storage elements 9. Assuming each sample of the received signal comprises B bits, the filter 7 requires Mxc3x97B bits of memory for storing the received signal and Mxc3x97H bits of memory for storing the generated PN sequence p(0) through p(Mxe2x88x921). Therefore, the amount of memory needed for the correlator shown in FIG. 2 is less than the amount needed for the correlation scheme represented by FIG. 1. Essentially, the amount of memory needed for the correlator of FIG. 2 is Wxc3x97B bits less than the amount of memory required for the correlation scheme represented by FIG. 1. However, W normally is small in comparison to M. Therefore, the reduction in the amount of memory needed for implementation of the correlator shown in FIG. 2 is not extremely significant.
Once the last sample r(Mxe2x88x921) has arrived, each sample is multiplied by its respective PN code sample by multipliers 10. The products are then summed by accumulator 11 to produce the correlation results C(0) through C(W). These operations are mathematically defined by Equation (2). M multiplications and Mxe2x88x921 additions are performed per input sample in order for the process to meet the real-time requirements. Therefore, the processor that performs the multiplication and addition operations must be fast enough to perform M multiplications and Mxe2x88x921 additions per input sample period, which can be difficult to achieve. For each new sample of the received signal, all of the multiplications and additions must be performed during the sample period. This is a large amount of processing to be performed in a very short time interval.
Also, although the correlator shown in FIG. 2 performs the correlation process in real-time, it is not time-efficient. The processor is only active for W chips, or sample times, out of the total number of sample times, M+Wxe2x88x921. For example, if the coherent integration length (M) is 1000 and the search window (W) is 100, the processor is only active about 9% of the time (i.e., 100/1,099). Therefore, the correlator of FIG. 2 does not utilize its resources in a time-efficient manner because it is only active a small percentage of the time, and when it is active, it must perform all of the calculations within a very small time interval.
Accordingly, a need exists for a correlator that is capable of time-efficient performance of the correlation process in real-time and that has relatively small memory requirements in comparison to the aforementioned correlators.
The present invention provides a time-efficient real-time correlator for use in a receiver of a wireless communications system. The correlator correlates a signal received by the receiver with a pseudo-random number (PN) code in order to determine the time delay of the received signal. The correlator requires no memory for storing samples of the received signal. A shift register having only W storage elements is utilized for storing the samples of the PN code sequence, where W is a positive integer corresponding to the length of the correlation window. Storage elements equal in number to W+1 are utilized for storing correlation result values.
When the correlator receives a current sample r(j) of the incoming signal, the current sample r(j) is multiplied by each of the samples of the PN code sequence to obtain products. The correlation result values stored in the correlation results storage elements are added to the products and the resulting sum is stored in the correlation results storage elements. Once M samples of the received signal have been correlated with the PN code samples, the correlation result values contained in the correlation results storage elements are mature. These correlation result values may then be processed to determine the time delay of the received signal. The correlator has increased throughput and decreased memory requirements, thereby enabling real-time operations to be performed in a time-efficient manner while also requiring fewer resources.
These and other features and advantages of the present invention will become apparent from the following description, drawings and claims.